chunk

malloc拿到的那塊chunk是一個header + data
因為size alignment的機制heap會以16(0x10)個bytes為基準去對齊

• Allocated chunk: malloc拿到的
• Free chunk: 釋放掉的chunk，未被重新使用
• Top chunk: 未被分配的

chunk header (metadata)

Allocated chunk

• pointer指在user data的地方，不是header
• 第一個8bytes，prev_size: 連續記憶體上一塊如果是free chunk，則記錄size，如果是allocated chunk則同時為他的data
• 第二個8bytes是size，代表這個chunk的大小，pointer沒有size的資訊，所以pointer就會指到header，就可以藉由這個pointer-8來知道這個chunk的size(包含flags)
• chunk size with 3 flags
  • 每個flags佔一個bit
  • 4個bit裡有一個沒有用到(保留位元)
  • 第0個bit是P(PREV_INUSE)
    • 如果這個bit是1，上一個chunk是allocated chunk，已經被分配出去正在使用中
    • 如果是0，表示前一個chunk是free的，那這個chunk的開頭就有一個prev_size 欄位(所以才能合併）
  • 第1個bit是M(IS_MMAPED)
    • chunk是否是透過mmap出來的
  • 第2個bit是N(NON_MAIN_ARENA)
    • 這個chunk是不是不屬於main arena
      

Free chunk

• 如果把chunk free掉，user data就不會被用到
• user data可以存metadata
• chunk free掉以後，除了header，data的前16個bytes也被存了兩個metadata分別是fd跟bk
  • fd(forward) : 指向 bin 中下一個chunk(靠近 list 尾端）
  • bk(back) : 指向 bin 中前一個chunk(靠近 list 頭端）
• fd跟bk不是連續記憶體的前一塊跟後一塊，是linked list鍊上的
  

Top chunk

• 第一次malloc後，剩下的空間為top chunk，分配空間時視情況從top chunk切割分配
• free Top chunk連續記憶體上一塊chunk時，若不是fastbin則會與Top chink merge，top chunk PREV_INUSE恆為1
  

bin

• 回收free chunk的資料結構
• 主要依據size的大小，分為:
  • fast bin
  • small bin
  • large bin
  • unsorted bin

Fast bin

• size < 0x90 bytes
• bin中依據size劃分為，0x20，0x30，0x40...
  • global_max_fast = 0x80
• Sinaly linked list，fd指向前一個，bk沒用到
• LIFO(Last in, First OUT)
• free時不會將下一塊chunk P flag設為0

Small bin

• Circular doubly linked list
• 依據size劃分為62個bin
  • 0x20，0x30 ~ 0x3f0(1008)
  • 0x20 ~ 0x80的大小與fast bin重疊，會根據機制放到fast bin or small bin
• FIFO(First in, First out)
• free掉時會將下一塊chunk P設為0

Large bin

• Circular doubly linked list(依據大小遞減排序)
  
• size >= 1024bytes(0x400)
• 63 bins
• 多了兩個metadata(header)
  • fd_nextsize
  • bk_nextsize

Unsorted bin

• Circular doubly linked list
• free的chunk size>fast bin時，不會直接放到對應的bin裡，會先丟到unsorted bin中
• malloc fast bin size大小時會先去fast bin list裡，若沒有則會至unsorted bin找，如找到一樣大小則回傳，若無但找到大小大於所需大小的chunk則切割回傳，剩下的部分會丟回unsorted bin，若都沒有則從top chunk切出來回傳